{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort Array by Increasing Frequency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: frequencySort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按照频率将数组升序排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，请你将数组按照每个值的频率 <strong>升序</strong> 排序。如果有多个值的频率相同，请你按照数值本身将它们 <strong>降序</strong> 排序。 </p>\n",
    "\n",
    "<p>请你返回排序后的数组。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,1,2,2,2,3]\n",
    "<b>输出：</b>[3,1,1,2,2,2]\n",
    "<b>解释：</b>'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,3,1,3,2]\n",
    "<b>输出：</b>[1,3,3,2,2]\n",
    "<b>解释：</b>'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [-1,1,-6,4,5,-6,1,4,1]\n",
    "<b>输出：</b>[5,-1,4,4,-6,-6,1,1,1]</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>-100 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-array-by-increasing-frequency](https://leetcode.cn/problems/sort-array-by-increasing-frequency/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-array-by-increasing-frequency](https://leetcode.cn/problems/sort-array-by-increasing-frequency/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2,2,2,3]', '[2,3,1,3,2]', '[-1,1,-6,4,5,-6,1,4,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key = lambda x : (nums.count(x), -x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt=Counter(nums)\n",
    "        nums.sort(key=lambda x:(cnt[x],-x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key=lambda x: (nums.count(x), -x))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        s=Counter(nums)\n",
    "        nums.sort(key=lambda x: (s[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        counter = Counter(nums)\n",
    "        return sorted(nums,key=lambda x: (counter[x],-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        d = {}\n",
    "        for num in nums:\n",
    "            if num in d:\n",
    "                d[num] += 1\n",
    "            else:\n",
    "                d[num] = 1\n",
    "        res = []\n",
    "        for i in d:\n",
    "            res.append([d[i], -i])\n",
    "        res.sort()\n",
    "        ans = []\n",
    "        for r in res:\n",
    "            ans += [-r[1]] * r[0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dict={}\n",
    "        for num in nums:\n",
    "            if num in dict:\n",
    "                dict[num]+=1\n",
    "            else:\n",
    "                dict[num]=1\n",
    "        sorted_nums = sorted(nums, key=lambda x: (dict[x], -x))\n",
    "        return sorted_nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        a = defaultdict(int)\n",
    "\n",
    "        for i in nums:\n",
    "            a[i]+=1\n",
    "\n",
    "        res = [(key, val) for key, val in a.items()]\n",
    "        res.sort(key=lambda x:(x[1], -x[0]))\n",
    "        # print(res)\n",
    "        out = []\n",
    "        for tup in res:\n",
    "            out+=[tup[0]]*tup[1]\n",
    "\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x:(cnt[x],-x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key=lambda x:(nums.count(x), -x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        freq=Counter(nums)\n",
    "        nums.sort(key=lambda x:(freq[x],-x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        c = collections.Counter(nums)\n",
    "        nums.sort(key=lambda x: (c[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        return sorted(nums, key=lambda x: (cnt[x], -x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x: (nums.count(x),-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        counter = Counter(nums)\n",
    "        return sorted(nums,key=lambda x: (counter[x],-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dic =  Counter(nums)\n",
    "        nums.sort(key = lambda x: (dic[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        c = Counter(sorted(nums))\n",
    "        res = []\n",
    "        for x in c.most_common():\n",
    "            res.extend([x[0]] * x[1])\n",
    "        return list(reversed(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        c = Counter(nums)\n",
    "        nums.sort(key = lambda n:(c[n], -n))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x:(cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt= Counter(nums)\n",
    "        nums.sort(key = lambda x:(cnt[x],-x))\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        a = Counter(nums)\n",
    "        nums.sort(key=lambda x:(a[x],-x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        m={}\n",
    "        for i in nums:\n",
    "            if m.get(i)==None:\n",
    "                m[i]=0\n",
    "            m[i]+=1\n",
    "        nums=sorted(nums,key=lambda x:(m[x],-x))\n",
    "        \n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        freq_dict = {}\n",
    "        for num in nums:\n",
    "            freq_dict[num] = freq_dict.get(num, 0) + 1\n",
    "        res = sorted(nums, key = lambda x: (freq_dict[x], -x))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dic = Counter(nums)\n",
    "        def custom_sort(item):\n",
    "            return dic[item], -item\n",
    "        nums.sort(key = custom_sort)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        c = Counter(nums)\n",
    "        frequency_dictionary = dict()\n",
    "        for key, value in c.items():  # 循环体部分可以使用collections.defaultdict优化（可以省去判断部分）\n",
    "            if value in frequency_dictionary.keys():\n",
    "                frequency_dictionary[value].append(key)\n",
    "            else:\n",
    "                frequency_dictionary[value] = [key]\n",
    "        # print(frequency_dictionary)\n",
    "\n",
    "        ans = list()\n",
    "        # print(sorted(frequency_dictionary))\n",
    "        for num in sorted(frequency_dictionary):  # 按字典中的键的升序顺序取出其对应值（数据类型: 列表）的各元素\n",
    "            frequency_dictionary[num].sort(reverse = True)  # 将字典的各值中的元素降序排列\n",
    "            for number in frequency_dictionary[num]:\n",
    "                ans.extend([number] * num)  # 将每个数乘以出现次数后添加到 ans 中\n",
    "        return ans\n",
    "'''\n",
    "  输入: nums = [-1,2,-6,4,5,-6,3,4,3,-6,-4,5,8,3,-1,-2,9,7]\n",
    "  标准输出:\n",
    "    {2: [-1, 4, 5], 1: [2, -4, 8, -2, 9, 7], 3: [-6, 3]}\n",
    "    [1, 2, 3]\n",
    "  输出: [9,8,7,2,-2,-4,5,5,4,4,-1,-1,3,3,3,-6,-6,-6]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        num_frequency = Counter(nums)\n",
    "\n",
    "        value_count = collections.defaultdict(list)\n",
    "        for key, value in num_frequency.items():\n",
    "            value_count[value].append(key)\n",
    "        \n",
    "        result = []\n",
    "        for key in sorted(value_count.keys()):\n",
    "            if len(value_count[key]) > 1:\n",
    "                for i in sorted(value_count[key], reverse=True):\n",
    "                    result += [i] * key\n",
    "            else:\n",
    "                result += [value_count[key][0]] * key\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums):\n",
    "        return sorted(nums, key=lambda x: (nums.count(x), -x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x:(nums.count(x),-x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x: (nums.count(x),-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        # return sorted(nums, key = lambda n: (nums.count(n), -n) )\n",
    "        cnt = Counter(nums)\n",
    "        return sorted(nums, key = lambda n: (cnt[n], -n))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        count = Counter(nums)\n",
    "        arr = []\n",
    "        for k, v in count.items():\n",
    "            arr.append([k, v])\n",
    "        arr.sort(key=lambda x: (x[1], -x[0]))\n",
    "        res = []\n",
    "        for a in arr:\n",
    "            res.extend([a[0] for _ in range(a[1])])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key = lambda x:(nums.count(x), -x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        counter = Counter(nums)\n",
    "        return sorted(nums,key=lambda x: (counter[x],-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        fMap = defaultdict(int)\n",
    "        for num in nums:\n",
    "            fMap[num] += 1\n",
    "        nums.sort(key=lambda x: (fMap[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key=lambda x: (cnt[x], -x))\n",
    "        return nums\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        freq = []\n",
    "        for num in nums:\n",
    "            freq.append(nums.count(num))\n",
    "        ans = sorted(zip(freq, nums), key = lambda x: (x[0], -x[1]))\n",
    "\n",
    "        return list(map(lambda x: x[1], ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nums.sort(key = lambda x:(cnt[x],-x))\n",
    "        return nums\n",
    "        # cc= sorted(cnt.items(),key = lambda x:x[1])\n",
    "        # ans = []\n",
    "        # for k,c in cc:\n",
    "        #     ans.extend([k]*c)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        arr = [[] for i in range(101)]\n",
    "        cur = 0\n",
    "        dic = collections.Counter(nums)\n",
    "        for k,v in dic.items():\n",
    "            arr[v].append(k)\n",
    "        for i in range(101):\n",
    "            if arr[i]:\n",
    "                arr[i].sort(reverse=True)\n",
    "                for num in arr[i]:\n",
    "                    while dic[num] > 0:\n",
    "                        nums[cur] = num\n",
    "                        cur += 1\n",
    "                        dic[num] -= 1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        return sorted(nums, key=lambda x: (cnt[x], -x))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        coun = Counter(nums)\n",
    "        nums.sort(key = lambda x:(coun[x],-x))\n",
    "        return nums\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        count=dict()\n",
    "        for num in nums:\n",
    "            if num not in count:\n",
    "                count[num]=0\n",
    "            else:\n",
    "                count[num]+=1\n",
    "        lst1=[]\n",
    "        for key,val in count.items():\n",
    "            lst1.append((val,key))\n",
    "        for i in range(len(lst1)-1):\n",
    "            for j in range(len(lst1)-i-1):\n",
    "                if lst1[j][0]>lst1[j+1][0]:\n",
    "                    lst1[j],lst1[j+1]=lst1[j+1],lst1[j]\n",
    "                if lst1[j][0]==lst1[j+1][0] and lst1[j][1]<lst1[j+1][1]:\n",
    "                    lst1[j],lst1[j+1]=lst1[j+1],lst1[j]\n",
    "        lst2=[]\n",
    "        for i in lst1:\n",
    "            lst2.append((i[1],i[0]))\n",
    "        output=[]\n",
    "        for i in lst2:\n",
    "            for j in range(i[1]+1):\n",
    "                output.append(i[0])\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x: (nums.count(x),-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        h=[0]*201\n",
    "        for num in nums:\n",
    "            h[num+100]+=1\n",
    "        nums.sort(key=lambda x:(h[x+100],-x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dic =  Counter(nums)\n",
    "        nums.sort(key = lambda x: (dic[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x: (nums.count(x),-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "\n",
    "        nums.sort(key=lambda x:  (cnt[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key = lambda x: (mp[x],-x) if (mp:=Counter(nums)) else nums) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums, key = lambda x: (Counter(nums)[x],-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        count = {}\n",
    "        for num in nums:\n",
    "            if num in count:\n",
    "                count[num] += 1\n",
    "            else:\n",
    "                count[num] = 1\n",
    "        \n",
    "        numsList = [num for num in count]\n",
    "        numsList.sort(key = lambda x: (count[x], -x))\n",
    "        \n",
    "        res = []\n",
    "        for num in numsList:\n",
    "            res += [num] * count[num]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def frequencySort(self, nums):\n",
    "        m=Counter(nums)\n",
    "        r=list(sorted(m.items(),key=lambda item:(item[1],-item[0])))\n",
    "        res=[]\n",
    "        for i,j in r:\n",
    "            for _ in range(j):\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dic = Counter(nums)\n",
    "        lst = sorted([(-k, v) for k, v in dic.items()], key=lambda n: (n[1], n[0]))\n",
    "        ans = []\n",
    "        for k, v in lst:\n",
    "            ans += [-k] * v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        l = sorted(list(cnt.items()), key=lambda x: (x[1],-x[0]))\n",
    "        x = []\n",
    "        for (k,freq) in l:\n",
    "            x += [k]*freq\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        m = dict()\n",
    "        for num in nums:\n",
    "            if -num in m:\n",
    "                m[-num] += 1\n",
    "            else:\n",
    "                m[-num] = 1\n",
    "        m = sorted(m.items(), key = lambda x: (x[1], x[0]))\n",
    "        res = []\n",
    "        for num, freq in m:\n",
    "            res += [-num]*freq\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def frequencySort(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        import collections as c\n",
    "        dict_nums = c.Counter(nums)\n",
    "\n",
    "        dict_nums = sorted(dict_nums.items(), key=lambda  x: (x[1], -x[0]))\n",
    "        dict_nums = dict(dict_nums)\n",
    "        nums = []\n",
    "        for key, value in dict_nums.items():\n",
    "            for i in range(int(value)):\n",
    "                nums.append(int(key))\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        listall=[]\n",
    "        for c in range(1,len(nums)+1):\n",
    "            list=[]\n",
    "            for i in nums:\n",
    "                if nums.count(i)==c:\n",
    "                    list.append(i)\n",
    "            list.sort()\n",
    "            list.reverse()\n",
    "            listall.extend(list)\n",
    "            del(list)\n",
    "        return listall\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        check={}\n",
    "        for digit in nums:\n",
    "            if digit in check:\n",
    "                check[digit]+=1\n",
    "            else:\n",
    "                check[digit]=1\n",
    "        # res=[]\n",
    "        # while check:\n",
    "        #     max_key=min(check,key=check.get)\n",
    "        #     val=check[max_key]\n",
    "        #     for _ in range(val):\n",
    "        #         res.append(max_key)\n",
    "        #     del check[max_key]\n",
    "        nums.sort(key=lambda x: (check[x], -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "\n",
    "        check = collections.Counter(nums)\n",
    "\n",
    "        arrs = [x for x in check]\n",
    "        arrs = sorted(arrs, key = lambda x: [check[x],-x])\n",
    "\n",
    "        ans = []\n",
    "        for x in arrs:\n",
    "            ans += [x]*check[x]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "         return sorted(nums, key = lambda x: (Counter(nums)[x],-x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        a = defaultdict(int)\n",
    "\n",
    "        for i in nums:\n",
    "            a[i]+=1\n",
    "\n",
    "        res = [(key, val) for key, val in a.items()]\n",
    "        res.sort(key=lambda x:(x[1], -x[0]))\n",
    "        print(res)\n",
    "        out = []\n",
    "        for tup in res:\n",
    "            out+=[tup[0]]*tup[1]\n",
    "\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        freq = []\n",
    "        for num in nums:\n",
    "            freq.append([nums.count(num),num * (-1)])\n",
    "        freq.sort()\n",
    "        res = [f[1] * (-1) for f in freq]\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        h = {}\n",
    "        for i in nums:\n",
    "            if i in h:\n",
    "                h[i] += 1\n",
    "            else:\n",
    "                h[i] = 1\n",
    "        nums.sort(key=lambda x:(h[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        hashdict = Counter(nums)\n",
    "        nums.sort(key = lambda x :(hashdict[x], -x))\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        dic =  Counter(nums)\n",
    "        nums.sort(key = lambda x: (dic[x], -x))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x: (nums.count(x),-x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        d = Counter(nums)\n",
    "        return sorted(nums,key= lambda x : [d[x],-x])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        m = collections.Counter(nums)\n",
    "\n",
    "        nums.sort(key=  lambda x: (m.get(x), -x))\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frequencySort(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        nf = [(num, freq) for num, freq in cnt.items()]\n",
    "        nf.sort(key=lambda x: (x[1], -x[0]))\n",
    "        ans = []\n",
    "        for num, freq in nf:\n",
    "            ans += [num] * freq\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
